home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / SciAn / src / ScianDatabase.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-02  |  26.6 KB  |  1,091 lines
  1. /* 
  2.    Tzong-Yow hwu
  3.    need changes to make:
  4.    1. keep the number of deleted nodes of the NameTree for reconstruction
  5.       the NameTree
  6. */
  7. #include "Scian.h"
  8. #include "ScianTypes.h"
  9. #include "ScianIDs.h"
  10. #include "ScianLists.h"
  11. #include "ScianSymbols.h"
  12. #include "ScianGarbageMan.h"
  13. #include "ScianDatabase.h"
  14.  
  15. #define DB_MAXKEYS  30 /* maximum number of keys allowed in the search key list */
  16.  
  17. struct LListNode 
  18. {
  19.   struct LListNode *next;
  20.   Bool isVolatile;      /* if it's a volatile object */
  21.   ObjPtr object;
  22. };
  23. struct NameTreeNode
  24. {
  25.   struct NameTreeNode *left;
  26.   struct NameTreeNode *right;
  27.   struct LListNode *list;
  28.   char *name;   
  29.   int linkLength;
  30.  /* the maximum number of link length of its left and right child */
  31.   Bool deleteFlag;
  32. };
  33. typedef struct LListNode llistNode;
  34. typedef struct NameTreeNode nameTreeNode;
  35. typedef enum {FAILED = 0, SUCCESSANDNOMORE = 1, SUCCESSANDMORE = 2} Triad;
  36.  
  37. /* a dummy object to be associated with the database system */
  38. static ObjPtr gcObject;
  39. static nameTreeNode *NameTree; 
  40. static llistNode *ClassList[N_CLASS_IDS + 1];  
  41. /* class id starting from 1 
  42.    Use 0th array element for objects whose class var is NULLOBJ */
  43.  
  44. #ifdef PROTO
  45.  
  46. static Triad addToNameTree(nameTreeNode **root, llistNode *listNode, char *name);
  47. static Bool deleteFromNameTree(ObjPtr object, char *name);
  48. static ObjPtr searchNameTree(char *name, int nKeys, NameTyp *keyId, ObjPtr *keyObj);
  49. static nameTreeNode *createNameTreeNode(llistNode *node, char *objname);
  50. static void freeNameTreeNode(nameTreeNode *node);
  51.  
  52. static Bool addToClassArray(llistNode *node, int classid);
  53. static Bool deleteFromClassArray(ObjPtr object, int classid);
  54. static ObjPtr searchClassArray(int classid, int nKeys, NameTyp *keyId, ObjPtr *keyObj);
  55. static ObjPtr dumbSearch(int nKeys, NameTyp *keyId, ObjPtr *keyObj);
  56.  
  57. static llistNode *createLListNode(ObjPtr object);
  58. static void freeLListNode(llistNode *node);
  59. static void addToLList(llistNode **list, llistNode *node);
  60. static Bool deleteFromLList(llistNode **list, ObjPtr object);
  61. static ObjPtr searchLList(llistNode *list, int nKeys, NameTyp *keyId, ObjPtr *keyObj);
  62.  
  63. static Bool matched(ObjPtr object, int nKeys, NameTyp *keyId, ObjPtr *keyObj);
  64.  
  65. #else
  66.  
  67. static Triad addToNameTree();
  68. static Bool deleteFromNameTree();
  69. static ObjPtr searchNameTree();
  70. static nameTreeNode *createNameTreeNode();
  71. static void freeNameTreeNode();
  72.  
  73. static Bool addToClassArray();
  74. static Bool deleteFromClassArray();
  75. static ObjPtr searchClassArray();
  76. static ObjPtr dumbSearch();
  77.  
  78. static llistNode *createLListNode();
  79. static void freeLListNode();
  80. static void addToLList();
  81. static Bool deleteFromLList();
  82. static ObjPtr searchLList();
  83.  
  84. static Bool matched();
  85.  
  86. #endif
  87.  
  88. /**************************** DATABASE OPERATIONS ***************************/
  89. #ifdef PROTO
  90. Bool AddToDatabase(ObjPtr object, Bool isVolatile)
  91. #else
  92. Bool AddToDatabase(object, isVolatile)
  93. ObjPtr object;
  94. Bool isVolatile;
  95. #endif
  96. {
  97.   ObjPtr var;
  98.   char *name;
  99.   char *empty = "";
  100.   int noclass = 0;
  101.   int classid;
  102.   llistNode *nameTreeListNode, *classArrayListNode;
  103.  
  104.   if (!object)
  105.     return false;
  106.  
  107.   /* figure out the name of the object */
  108.   MakeVar(object, NAME);
  109.   var = GetVar(object, NAME);
  110.   if (!var)
  111.     {
  112.       /* var is a NULLOBJ */
  113.       name = empty;
  114.     }
  115.   else
  116.     {
  117.       name = GetString(var);
  118.     }
  119.  
  120.   /* figure out the classid of the object */
  121.   MakeVar(object, CLASSID);
  122.   var = GetVar(object, CLASSID);
  123.   if (!var)
  124.     {
  125.       classid = noclass;
  126.     }
  127.   else
  128.     {
  129.       classid = GetInt(var);
  130.     }
  131.  
  132.   /* make a ClassArrayListNode and a NameTreeListNode and insert them
  133.      into the NameTree and ClassArray respectively */
  134.   if (!(nameTreeListNode = createLListNode(object)))
  135.     {
  136.       return false;
  137.     }
  138.   if (!(classArrayListNode = createLListNode(object)))
  139.     {
  140.       freeLListNode(nameTreeListNode);
  141.       return false;
  142.     }
  143.  
  144.   /* set up volatile flag */
  145.   nameTreeListNode->isVolatile = classArrayListNode->isVolatile = isVolatile;
  146.  
  147.   if (FAILED == addToNameTree(&NameTree, nameTreeListNode, name) || 
  148.       false == addToClassArray(classArrayListNode, classid))
  149.     {
  150.       freeLListNode(nameTreeListNode);
  151.       freeLListNode(classArrayListNode);
  152.       return false;
  153.     }
  154.   return true;
  155. } /* AddToDatabase */
  156.  
  157. #ifdef PROTO
  158. Bool DeleteObjFromDatabase(ObjPtr object)
  159. #else
  160. Bool DeleteObjFromDatabase(object)
  161. ObjPtr object;
  162. #endif
  163. /* The deleteFlag of a Nametreenode is turned on if it has an empty
  164.    list, i.e., the list ptr points to null */
  165. {
  166.   char *name;
  167.   char *empty = "";
  168.   ObjPtr var;
  169.   int classid;
  170.   int noclass = 0;
  171.   llistNode *treeListNode, classArrayListNode;
  172.  
  173.   if (!object)
  174.     return false;
  175.  
  176.   MakeVar(object, NAME);
  177.   var = GetVar(object, NAME);
  178.   if (!var)
  179.     {
  180.       /* var is a NULLOBJ */
  181.       name = empty;
  182.     }
  183.   else
  184.     {
  185.       name = GetString(var);
  186.     }
  187.  
  188.   MakeVar(object, CLASSID);
  189.   var = GetVar(object, CLASSID);
  190.   if (!var)
  191.     {
  192.       classid = noclass;
  193.     }
  194.   else
  195.     {
  196.       classid = GetInt(var);
  197.     }
  198.  
  199.   /* if the object is not in the name tree, it should not be in the 
  200.      class array either */
  201.   if (!deleteFromNameTree(object, name))
  202.     {
  203.       if (deleteFromClassArray(object, classid))
  204.     {
  205.       ReportError("DeleteObjFromDatabase", "database is in inconsistent state");
  206.     }
  207.       /* 
  208.      Is ther a need to report an error if the object is not in the database 
  209.       else
  210.     {
  211.           ReportError("DeleteObjFromDatabase", "object not found");
  212.         }
  213.       */
  214.       return false;
  215.     }
  216.   if (!deleteFromClassArray(object, classid))
  217.     {
  218.       ReportError("DeleteObjFromDatabase", "database is in inconsistent state");
  219.       return false;
  220.     }
  221.  
  222.   return true;
  223. } /* DeleteObjFromDatabase */
  224.  
  225. #ifdef PROTO
  226. ObjPtr SearchDatabase(ObjPtr keylist)
  227. #else
  228. ObjPtr SearchDatabase(keylist)
  229. ObjPtr keylist;
  230. #endif
  231. /* if there is Name primarily search by NAME,
  232.    else if there is CLASSID primarily search by CLASSID,
  233.    else performs a linear search on the class array by the keys present */
  234. /* returns NULLOBJ if error, an emptylist if not found, a list otherwise */
  235. {
  236.   char *emptyname = "";
  237.   Bool isName = false;          /* is name there as a key in the list */
  238.   char *name;
  239.  
  240.   ObjPtr classObj;
  241.   Bool isClassid = false;       /* is class id there as a key in the list */
  242.   int classid;
  243.   int noclass = 0;
  244.  
  245.   /* construct an array of name types corresponding to keylist */
  246.   NameTyp keyId[DB_MAXKEYS]; 
  247.   /* construct an array of objptr from keylist */
  248.   ObjPtr keyObj[DB_MAXKEYS];
  249.  
  250.   int index;
  251.   int keyIndex;
  252.   int nKeys;
  253.   int nElements;
  254.  
  255.   if (!keylist)
  256.     {
  257.       /* keylist is a NULLOBJ */
  258.       return dumbSearch(0, (NameTyp *) 0, (ObjPtr *) 0);
  259.     }
  260.   else if (!IsList(keylist) || ((nElements=ListCount(keylist)) % 2))
  261.     {
  262.       /* keylist must be a nonempty list and has even number of elements */
  263.       ReportError("SearchDatabase", "Improper key list");
  264.       return NULLOBJ;
  265.     }
  266.   else if (nElements == 0)
  267.     {
  268.       /* empty key list, return the whole database */
  269.       return dumbSearch(0, (NameTyp *) 0, (ObjPtr *) 0);
  270.     }
  271.   else if ((nKeys = nElements / 2) > DB_MAXKEYS)
  272.     {
  273.       ReportError("SearchDatabase", "Exceeds the maximum number of allowed keys");
  274.       return NULLOBJ;
  275.     }
  276.  
  277.   keyIndex = 0;
  278.   for (index = 0; index < nKeys; index++)
  279.     {
  280.       ObjPtr symbol;
  281.       ObjPtr obj;
  282.       NameTyp id;
  283.  
  284.       symbol = GetListElem(keylist, 2 * index);
  285.       obj = GetListElem(keylist, 2 * index + 1);
  286.       if (!IsSymbol(symbol))
  287.     {
  288.           ReportError("SearchDatabase", "Improper key list");
  289.           return NULLOBJ;
  290.     }
  291.       id = GetSymbolID(symbol);
  292.       
  293.       if (id == NAME)
  294.     {
  295.           if (isName == true)
  296.         {
  297.           ReportError("SearchDatabase", "Double NAME keys in keylist");
  298.           return NULLOBJ;
  299.         }
  300.       if (!obj)
  301.         {
  302.           name = emptyname;
  303.             }
  304.           else if (!IsString(obj))
  305.         {
  306.           ReportError("SearchDatabase", "non-string obj after NAME symbol");
  307.           return NULLOBJ;
  308.         }
  309.           else
  310.         {
  311.           name = GetString(obj);
  312.         }
  313.           if (!name)
  314.         name = emptyname;
  315.       isName = true;  
  316.     }
  317.       else if (id == CLASSID)
  318.     {
  319.       if (isClassid == true)
  320.         {
  321.           ReportError("SearchDatabase", "Double CLASSID keys in keylist");
  322.           return NULLOBJ;
  323.         }
  324.       if (!obj)
  325.         {
  326.           classid = noclass;
  327.         }
  328.       else if (!IsInt(obj))
  329.         {
  330.           ReportError("SearchDatabase", "non-class obj after CLASS symbol");
  331.           return NULLOBJ;
  332.         }
  333.           else
  334.         {
  335.           classid = GetInt(obj);
  336.         }
  337.           if (classid > N_CLASS_IDS || classid < 0)
  338.         {
  339.           ReportError("SearchDatabase", "Class id exceeds range");
  340.           return NULLOBJ;
  341.         }
  342.       classObj = obj;
  343.           isClassid = true;
  344.     }
  345.       else
  346.     {
  347.           keyId[keyIndex] = id;
  348.           keyObj[keyIndex] = obj;
  349.       keyIndex++;
  350.     }
  351.     }
  352.   /* the search routines always return a list obj or NULLOBJ if failed */
  353.   if (isName)
  354.     {
  355.       if (isClassid)
  356.     {
  357.       keyId[keyIndex] = CLASSID;
  358.       keyObj[keyIndex] = classObj;
  359.     }
  360.          /* NAME key is not included */
  361.       return searchNameTree(name, nKeys - 1, keyId, keyObj);
  362.     }
  363.   else if (isClassid)
  364.     {
  365.          /* CLASSID key is not included */
  366.       return searchClassArray(classid, nKeys - 1, keyId, keyObj);
  367.     }
  368.   else
  369.     {
  370.       return dumbSearch(nKeys, keyId, keyObj);
  371.     }
  372. }
  373.  
  374. /* method use only old way of c function definition */
  375. ObjPtr MarkDatabase(gcObject)
  376. ObjPtr gcObject;
  377. {
  378.   /* it's sufficient to mark all the objects in the Class Array */
  379.   /* easier to traverse */
  380.   int i;
  381.   llistNode *runner;
  382.  
  383.   for (i = 0; i <= N_CLASS_IDS; i++)
  384.      for (runner = ClassList[i]; runner; runner = runner->next)
  385.     {
  386.       if (runner->isVolatile == DB_NONVOLATILE)
  387.         {
  388.           MarkObject(runner->object);
  389.         }
  390.     }
  391.   return ObjTrue;
  392. } /* MarkDatabase */
  393.  
  394. #ifdef PROTO
  395. void InitDatabase(void)
  396. #else
  397. void InitDatabase()
  398. #endif
  399. {
  400.   int i;
  401.  
  402.   gcObject = NewObject(NULLOBJ, 0);
  403.   AddToReferenceList(gcObject);
  404.   SetMethod(gcObject, MARK, MarkDatabase);
  405.  
  406.   /* empty database, do an initialization first */
  407.   NameTree = (nameTreeNode *) 0;
  408.   for (i = 0; i <= N_CLASS_IDS; i++)
  409.      {
  410.        ClassList[i] = (llistNode *) 0;
  411.      }
  412.   return;
  413. } /* InitDatabase */
  414.  
  415. #ifdef PROTO
  416. void KillDatabase(void)
  417. #else
  418. void KillDatabase()
  419. #endif
  420. {
  421.   RemoveFromReferenceList(gcObject);
  422.   return;
  423. } /* KillDatabase */
  424.  
  425.  
  426. /**************************** NameTree Operations ****************************/
  427. /* 
  428.    This is a recursive algorithm for adding a node into a binary tree and
  429.    maintain its balance.  Balance in this case means the difference between
  430.    any node's left and right link length is not greater than 1.
  431.  
  432.    When adding a linked-list node into the binary NameTree, three possible
  433.    results may occur:
  434.    0. Error iff an name tree node is not able be allocated or name is a 
  435.       null pointer.
  436.    1. Success and the list node is inserted into the linked list of an
  437.       already existing tree node. 
  438.    2. Success and a new tree node is created to accomdate this list node.
  439.  
  440.       For case 2, a new node is created and the balance of the binary tree
  441.       needed to be maintained.  The flow of op is like this: 
  442.       When the length of the current node changed, we let the parent
  443.       to determine whether it needs to balance its subtree by returning
  444.       SUCCESSANDMORE value.  Upon receiving the return value of 
  445.       SUCCESSANDMORE, the current node look into its rightlength and
  446.       leftlength for determining successive actions. ? possible actions: 
  447.  
  448.       1. When the length of left or right child changed and their difference 
  449.          is greater than 1, we need to balance the subtree rooted at the
  450.          current node.  After a balancing op, the length of the current node
  451.          may be different.  Return accordingly.
  452.       2. When their difference is not greater than 1, the current node needs 
  453.          to determine whether it needs to increment its length by 1.  
  454.          If YES, return SUCCESSANDMORE.
  455.          If NO, return SUCCESSANDNOMORE.
  456. */
  457. #ifdef PROTO
  458. static Triad addToNameTree(nameTreeNode **root, llistNode *listNode, char *name)
  459. #else
  460. static Triad addToNameTree(root, listNode, name)
  461. nameTreeNode *root;
  462. llistNode *listNode;
  463. char *name;
  464. #endif
  465. {
  466.   int direction;
  467.   Triad retVal;
  468.  
  469.   if (!name)
  470.     return FAILED;
  471.  
  472.   if (!*root)
  473.     {
  474.       if ( !(*root = createNameTreeNode(listNode, name)) )
  475.         return FAILED;
  476.       return SUCCESSANDMORE;
  477.     }
  478.  
  479.   direction = strcmp2((*root)->name, name);
  480.  
  481.   if (!direction)
  482.     {
  483.       if ((*root)->deleteFlag == true)
  484.         {
  485.           (*root)->deleteFlag = false;
  486.         }
  487.       addToLList(&(*root)->list, listNode);
  488.       return SUCCESSANDNOMORE;
  489.     }
  490.   else if (direction < 0)
  491.     {
  492.       if ( SUCCESSANDMORE == 
  493.             (retVal = addToNameTree(&((*root)->right), listNode, name)) )
  494.         { 
  495.           /* The root's right link length is just incremented by 1, see
  496.              if we need to do the balancing task, or changing the link length
  497.              of the root and returns SUCCESSANDMORE */
  498.  
  499.           int leftLength, rightLength;
  500.  
  501.           /* determine the left and right length */ 
  502.           leftLength = (*root)->left ? (*root)->left->linkLength : 0;
  503.           /* there must be a right child since we just added one */
  504.           rightLength = (*root)->right->linkLength; 
  505.  
  506.           /* Check the length difference first and balancing accordingly */ 
  507.           /* the length diff may only one of three possible values 0, 1, 2 */
  508.           switch(rightLength - leftLength)
  509.             {
  510.               case 0:
  511.                     /* Before adding the node, the situation is that
  512.                        leftLength is 1 greater than rightLength, 
  513.                        the link length of the root must be leftLength + 1 */
  514.                     /* balanced and no need to change link length, do nothing */
  515.                      retVal = SUCCESSANDNOMORE;
  516.                      break;
  517.               case 1: 
  518.                      /* Before adding the node, the situation is that
  519.                         rightLength is the same as leftLength */
  520.                      /* rightLength - leftLength must be 1 after adding
  521.                         the node to the right and get its rightlength
  522.                         incremented by 1. */
  523.                      (*root)->linkLength += 1;
  524.                      retVal = SUCCESSANDMORE;
  525.                      break;
  526.               case 2:
  527.                   {
  528.                      /* Before adding the node, the situation is that
  529.                         rightLength = leftLength + 1, the link length of the 
  530.                         root must be old rightLength + 1 that is the current
  531.                         value of rightlength */
  532.                      /* needs balancing */
  533.                      nameTreeNode *temp;  
  534.                      int newRightLength;
  535.                       
  536.                      temp = *root;
  537.                      *root = (*root)->right;
  538.                      temp->right = (*root)->left;
  539.                      (*root)->left = temp;
  540.                      
  541.                      /* after the switching, we need calculate the linklength
  542.                         of the node currently pointed by temp, which is the
  543.                         left child of the *root now.  */
  544.                      /* The result of newRightLength - leftLength is either
  545.                         0 or 1.  That's what the balancing for. */
  546.                      newRightLength = temp->right ? temp->right->linkLength : 0;
  547.                      if (newRightLength == leftLength)
  548.                        {
  549.                          temp->linkLength -= 1;
  550.                          retVal = SUCCESSANDNOMORE;
  551.                        }
  552.                      else
  553.                        {
  554.                          (*root)->linkLength += 1;
  555.                          retVal = SUCCESSANDMORE;
  556.                        } 
  557.                   }
  558.                      break;
  559.               default: 
  560.                      /* dummy case */
  561.                      break;
  562.             }
  563.         } 
  564.       return retVal;
  565.     }
  566.   else
  567.     {
  568.       if ( SUCCESSANDMORE == 
  569.             (retVal = addToNameTree(&((*root)->left), listNode, name)) )
  570.         {
  571.           int leftLength, rightLength;
  572.  
  573.           rightLength = (*root)->right ? (*root)->right->linkLength : 0;
  574.           leftLength = (*root)->left->linkLength; 
  575.  
  576.           switch(leftLength - rightLength)
  577.             {
  578.               case 0:
  579.                      retVal = SUCCESSANDNOMORE;
  580.                      break;
  581.               case 1: 
  582.                      (*root)->linkLength += 1;
  583.                      retVal = SUCCESSANDMORE;
  584.                      break;
  585.               case 2:
  586.                   {
  587.                      nameTreeNode *temp;  
  588.                      int newLeftLength;
  589.                       
  590.                      temp = *root;
  591.                      *root = (*root)->left;
  592.                      temp->left = (*root)->right;
  593.                      (*root)->right = temp;
  594.                      
  595.                      newLeftLength = temp->left ? temp->left->linkLength : 0;
  596.                      if (newLeftLength == rightLength)
  597.                        {
  598.                          temp->linkLength -= 1;
  599.                          retVal = SUCCESSANDNOMORE;
  600.                        }
  601.                      else
  602.                        {
  603.                          (*root)->linkLength += 1;
  604.                          retVal = SUCCESSANDMORE;
  605.                        } 
  606.                   }
  607.                      break;
  608.               default: 
  609.                      /* dummy case */
  610.                      break;
  611.             }
  612.         } 
  613.       return retVal;
  614.     }
  615. } /* addToNameTree */
  616.  
  617. /* This is an iteration algorithm for pseudo deleting a node from the 
  618.    name tree.  A node is pseudo deleted iff it has an empty linked list.
  619.    Pseudo deletion is done by turning on the deleteFlag of the tree node. */
  620. #ifdef PROTO
  621. static Bool deleteFromNameTree(ObjPtr object, char *name)
  622. #else
  623. static Bool deleteFromNameTree(object, name)
  624. ObjPtr object;
  625. char *name;
  626. #endif
  627. {
  628.   nameTreeNode *runner;
  629.   Bool retVal;
  630.  
  631.   runner = NameTree;
  632.   while(runner)
  633.     {
  634.       int direction;
  635.  
  636.       direction = strcmp2(runner->name, name);
  637.  
  638.       if (!direction)
  639.     {
  640.           if (runner->deleteFlag == true)
  641.         {
  642.           /* 
  643.          Is there a need to report an error when object no found. 
  644.                  ReportError("deleteFromNameTree", "object not found");
  645.               */
  646.           return false;
  647.             }
  648.       retVal = deleteFromLList(&runner->list, object);
  649.       if (!runner->list)
  650.         {
  651.           /* if there is no more nodes in the list, pseudo delete the node. */
  652.           runner->deleteFlag = true;
  653.         }
  654.       return retVal;
  655.     }
  656.       else if (direction < 0)
  657.     {
  658.       runner = runner->right; 
  659.     }
  660.       else
  661.     {
  662.       runner = runner->left; 
  663.     }
  664.     }/* while loop */
  665.  
  666.   /* 
  667.      Is there a need to report an error when object no found. 
  668.      ReportError("deleteFromNameTree", "object not found");
  669.   */
  670.   return false;
  671. } /* deleteFromNameTree */
  672.  
  673. #ifdef PROTO
  674. static ObjPtr searchNameTree(char *name, int nKeys, NameTyp *keyId, ObjPtr *keyObj)
  675. #else
  676. static ObjPtr searchNameTree(name, nKeys, keyId, keyObj)
  677. char *name;
  678. int nKeys;
  679. NameTyp *keyId;
  680. ObjPtr *keyObj;
  681. #endif
  682. {
  683.   nameTreeNode *runner;
  684.  
  685.   runner = NameTree;
  686.   while(runner)
  687.     {
  688.       int direction;
  689.  
  690.       direction = strcmp2(runner->name, name);
  691.  
  692.       if (!direction)
  693.     {
  694.           if (runner->deleteFlag == false)
  695.         {
  696.           return searchLList(runner->list, nKeys, keyId, keyObj);
  697.         }
  698.       else
  699.         {
  700.           return NewList();
  701.         }
  702.         }
  703.       else if (direction < 0)
  704.     {
  705.       runner = runner->right; 
  706.     }
  707.       else
  708.     {
  709.       runner = runner->left; 
  710.     }
  711.     }/* while loop */
  712.  
  713.   return NewList();
  714. } /* searchNameTree */
  715.  
  716. #ifdef PROTO
  717. static nameTreeNode *createNameTreeNode(llistNode *node, char *objname)
  718. #else
  719. static nameTreeNode *createNameTreeNode(node, objname)
  720. llistNode *node;
  721. char *objname;
  722. #endif
  723. /* Construct a new tree node and add node at the beginning of the tree node list */
  724. {
  725.   nameTreeNode *retVal;
  726.  
  727.   if (!(retVal = (nameTreeNode *) Alloc(sizeof(nameTreeNode))))
  728.     {
  729.       ReportError("createNameTreeNode", "out of memory");
  730.       return (nameTreeNode *) 0;
  731.     }
  732.  
  733.   if (!(retVal->name = (char *) Alloc((strlen(objname) + 1) * sizeof(char))))
  734.     {
  735.       Free(retVal);
  736.       ReportError("createNameTreeNode", "out of memory");
  737.       return (nameTreeNode *) 0;
  738.     }
  739.  
  740.   strcpy(retVal->name, objname);
  741.   retVal->left = (nameTreeNode *) 0;
  742.   retVal->right = (nameTreeNode *) 0;
  743.   retVal->list = node;
  744.   retVal->deleteFlag = false;
  745.   retVal->linkLength = 1; /* a newly created tree node is going to be 
  746.                              at the leaf position which is of link length
  747.                              1 */
  748.  
  749.   return retVal;
  750. } /* createNameTreeNode */
  751.  
  752. #ifdef PROTO
  753. static void freeNameTreeNode(nameTreeNode *node)
  754. #else
  755. static void freeNameTreeNode(node)
  756. nameTreeNode *node;
  757. #endif
  758. {
  759.   Free(node->name);
  760.   Free(node);
  761.   return;
  762. }
  763.  
  764.  
  765. /**************************** ClassArray Operations ****************************/
  766. #ifdef PROTO
  767. static Bool addToClassArray(llistNode *node, int classid)
  768. #else
  769. static Bool addToClassArray(node, classid)
  770. llistNode *node;
  771. int classid;
  772. #endif
  773. {
  774.   if (classid < 0 || classid > N_CLASS_IDS)
  775.     {
  776.       ReportError("addToClassArray", "Class id exceeds range");
  777.       return false;
  778.     }
  779.   else
  780.     {
  781.       addToLList(ClassList + classid, node);
  782.       return true;
  783.     }
  784. } /* addToClassArray */
  785.  
  786. #ifdef PROTO
  787. static Bool deleteFromClassArray(ObjPtr object, int classid)
  788. #else
  789. static Bool deleteFromClassArray(object, classid)
  790. ObjPtr object;
  791. int classid;
  792. #endif
  793. {
  794.   if (classid < 0 || classid > N_CLASS_IDS)
  795.     {
  796.       ReportError("deleteFromClassArray", "Class id exceeds range");
  797.       return false;
  798.     }
  799.   else
  800.     {
  801.       return deleteFromLList(ClassList + classid, object);
  802.     }
  803. } /* deleteFromClassArray */
  804.  
  805. #ifdef PROTO
  806. static ObjPtr searchClassArray(int classid, int nKeys, NameTyp *keyId, ObjPtr *keyObj)
  807. #else
  808. static ObjPtr searchClassArray(classid, nKeys, keyId, keyObj)
  809. int classid;
  810. int nKeys;
  811. NameTyp *keyId;
  812. ObjPtr *keyObj;
  813. #endif
  814. {
  815.   if (classid < 0 || classid > N_CLASS_IDS)
  816.     {
  817.       ReportError("searchClassArray", "Class id exceeds range");
  818.       return NULLOBJ;
  819.     }
  820.   else
  821.     {
  822.       return searchLList(ClassList[classid], nKeys, keyId, keyObj);
  823.     }
  824. }
  825.  
  826. #ifdef PROTO
  827. static ObjPtr dumbSearch(int nKeys, NameTyp *keyId, ObjPtr *keyObj)
  828. #else
  829. static ObjPtr dumbSearch(nKeys, keyId, keyObj)
  830. int nKeys;
  831. NameTyp *keyId;
  832. ObjPtr *keyObj;
  833. #endif
  834. {
  835.   int runner;
  836.   ObjPtr newlist;
  837.   ObjPtr retVal = NULLOBJ; 
  838.  
  839.   for (runner = 0; runner <= N_CLASS_IDS; runner++)
  840.      {
  841.        newlist = searchLList(ClassList[runner], nKeys, keyId, keyObj);
  842.        if (!newlist)
  843.      {
  844.        return NULLOBJ;
  845.      }
  846.        else
  847.      {
  848.        if (ListCount(newlist) > 0)
  849.          {
  850.            if (!retVal)
  851.          {
  852.            if (!(retVal = NewList()))
  853.              {
  854.                ReportError("dumbSearch", "Unable to get a new list");
  855.                return NULLOBJ;
  856.              }
  857.          }
  858.                AppendList(retVal, newlist); 
  859.          }
  860.      }
  861.      }
  862.   return retVal;
  863. }
  864.  
  865. /****************************** LList Operations *******************************/
  866.  
  867. #ifdef PROTO
  868. static llistNode *createLListNode(ObjPtr object)
  869. #else
  870. static llistNode *createLListNode(object)
  871. ObjPtr object;
  872. #endif
  873. {
  874.   llistNode *retVal;
  875.  
  876.   if (!(retVal = (llistNode *) Alloc(sizeof(llistNode))))
  877.     {
  878.       ReportError("createLListNode", "out of memory");
  879.       return (llistNode *) 0;
  880.     }
  881.   else
  882.     {
  883.       retVal->object = object;
  884.       retVal->next = (llistNode *) 0;
  885.       return retVal;
  886.     }
  887. } /* createLListNode */
  888.  
  889. #ifdef PROTO
  890. static void freeLListNode(llistNode *node)
  891. #else
  892. static void freeLListNode(node)
  893. llistNode *node;
  894. #endif
  895. {
  896.   Free(node);
  897.   return;
  898. } /* freeLListNode */
  899.  
  900. #ifdef PROTO
  901. static void addToLList(llistNode **list, llistNode *node)
  902. #else
  903. static void addToLList(list, node)
  904. llistNode **list;
  905. llistNode *node;
  906. #endif
  907. {
  908.   node->next = *list;
  909.   *list = node;
  910.  
  911.   return;
  912. }
  913.  
  914. #ifdef PROTO
  915. static Bool deleteFromLList(llistNode **list, ObjPtr object)
  916. #else
  917. static Bool deleteFromLList(list, object)
  918. llistNode **list;
  919. ObjPtr object;
  920. #endif
  921. {
  922.   llistNode *current, *previous;
  923.  
  924.   current = *list;
  925.  
  926.   while(current)
  927.     {
  928.       if (current->object == object)
  929.     /* object found */
  930.     {
  931.       /* at the beggining of the list */
  932.       if (current == *list)
  933.         {
  934.           *list = current->next;
  935.         }
  936.       /* somewhere after first node in the list */
  937.           else
  938.         {
  939.           previous->next = current->next;  
  940.         }
  941.           freeLListNode(current);
  942.       return true;
  943.     }
  944.       else
  945.     {
  946.       previous = current;
  947.       current = current->next;
  948.     }
  949.     }
  950.  
  951.   /* 
  952.      Is there a need to report that the object is not found within the list. 
  953.  
  954.      ReportError("deleteFromLList", "object not found");
  955.   */
  956.   return false;
  957. }
  958.  
  959. #ifdef PROTO
  960. static ObjPtr searchLList(llistNode *list, int nKeys, NameTyp *keyId, ObjPtr *keyObj)
  961. #else
  962. static ObjPtr searchLList(list, nKeys, keyId, keyObj)
  963. llistNode *list;
  964. int nKeys;
  965. NameTyp *keyId;
  966. ObjPtr *keyObj;
  967. #endif
  968. {
  969.   llistNode *runner;
  970.   ObjPtr retVal;
  971.  
  972.   if (!(retVal = NewList()))
  973.     {
  974.       ReportError("searchLList", "Unable to get a new list");
  975.       return NULLOBJ;
  976.     }
  977.  
  978.   runner = list;
  979.   while(runner)
  980.     {
  981.       if (true == matched(runner->object, nKeys, keyId, keyObj))
  982.         {
  983.           if (!PrefixList(retVal, runner->object))
  984.             {
  985.           ReportError("searchLList", "Unable to Prefix to list");
  986.               return NULLOBJ;
  987.             }
  988.     }
  989.       runner = runner->next;
  990.     }
  991.  
  992.   return retVal;
  993. }
  994.  
  995. /************************** matching operation ******************************/
  996.  
  997. #ifdef PROTO
  998. static Bool matched(ObjPtr object, int nKeys, NameTyp *keyId, ObjPtr *keyObj)
  999. #else
  1000. static Bool matched(object, nKeys, keyId, keyObj)
  1001. ObjPtr object;
  1002. int nKeys;
  1003. NameTyp *keyId;
  1004. ObjPtr *keyObj;
  1005. #endif
  1006. {
  1007.   Bool matched = true;
  1008.   int i;
  1009.  
  1010.   for (i = 0; matched && i < nKeys; i++)
  1011.     {
  1012.       ObjPtr varObj;
  1013.  
  1014.       MakeVar(object, keyId[i]);
  1015.       varObj = GetVar(object, keyId[i]);
  1016.  
  1017.       if (IsString(keyObj[i]))
  1018.     {
  1019.       if (!IsString(varObj))
  1020.         {
  1021.           return false; 
  1022.         }
  1023.           else
  1024.         {
  1025.           char *keyString, *varString;
  1026.  
  1027.           keyString = GetString(keyObj[i]);
  1028.           varString = GetString(varObj);
  1029.           matched = strcmp2(keyString, varString) ? false : true;
  1030.         }
  1031.     }
  1032.       else
  1033.     {
  1034.       matched = Equal(varObj, keyObj[i]);
  1035.     }
  1036.     }
  1037.  
  1038.   return matched;
  1039. }
  1040.  
  1041. #ifdef PROTO
  1042. ObjPtr NewUniqueName(char *oldName, int classID)
  1043. #else
  1044. ObjPtr NewUniqueName(oldName, classID)
  1045. char *oldName;
  1046. int classID;
  1047. #endif
  1048. /*Generates a new name based on oldName which does not conflict with existing
  1049.   objects of classID in the database*/
  1050. {
  1051.     char trialName[400];
  1052.     char *s;
  1053.     int k;
  1054.  
  1055.     if (!DatabaseConflict(oldName, classID))
  1056.     {
  1057.     return NewString(oldName);
  1058.     }
  1059.  
  1060.     strcpy(trialName, oldName);
  1061.  
  1062.     s = trialName;
  1063.     while (*s) ++s;
  1064.     while (s > trialName && isspace(*s)) *s-- = 0;
  1065.     --s;
  1066.     if (s > trialName && isdigit(*s)) --s;
  1067.     {
  1068.     while (s > trialName && isdigit(*s)) --s;
  1069.     if (s > trialName && *s == '#')
  1070.     {
  1071.         --s;
  1072.         while (s > trialName && isspace(*s)) --s;
  1073.         if (s >= trialName)
  1074.         {
  1075.         ++s;
  1076.         *s = 0;
  1077.         }
  1078.     }
  1079.     }
  1080.     while (*s) ++s;
  1081.  
  1082.     for (k = 2; ; ++k)
  1083.     {
  1084.     sprintf(s, " #%d", k);
  1085.     if (!DatabaseConflict(trialName, classID))
  1086.     {
  1087.         return NewString(trialName);
  1088.     }
  1089.     }
  1090. }
  1091.